This application claims priority under 35 U.S.C. xc2xa7xc2xa7119 and/or 365 to 198 38 865.9 filed in Federal Republic of Germany on Aug. 26, 1998; the entire content of which is hereby incorporated by reference.
The invention generally relates to the generation of a CRC (cyclic redundancy check) which is used for checking errors when transmitting digital data from a transmitter to a receiver. The CRC may have a different length and is added to the user data in the transmitter. In the receiver the CRC data is compared with the CRC data re-generated on the basis of the received user data. If the two generated CRCs match, then it is determined that no serious transmission errors have occurred during the transmission between transmitter and receiver.
The generation of a CRC code is a standard technique and circuits are known in the prior art for generating this CRC code either serially or parallely. As will be explained below with more detail, design tools are available for designing such serial and parallel generation circuits. However, so far it was not known that such design tools for the parallel CRC generation circuit did not take into account redundancies in the feedback lines. That is, if more feedback lines are used than absolutely necessary to perform the parallel CRC generation, then the hardware amount is extensive and the speed of parallely generating the CRC bits is decreased.
The present invention particularly relates to the problem of how the redundancies in the parallel CRC generation circuits can be reduced.
When designing a CRC generation circuit for generating a CRC code of length N, a CRC polynomial CRCN is used, which is generally defined by the following equation (1a):
CRCN=aNxN+aNxe2x88x921xNxe2x88x921+ . . . anxn+ . . . a1xn+a0x0xe2x80x83xe2x80x83(1a)
In this equation (1a) the coefficient aN=1, a0=1 and the coefficients an, n=1, . . . , Nxe2x88x921 are 0 or 1 depending on the CRC code to be formed. FIG. 1a shows the principle of a serial CRC generation circuit realized on the basis of the CRC polynomial in equation (1a). The CRC generation circuit comprises a number N of shift registers C0, C1, . . . , Cn, . . . , CNxe2x88x921 in series connection. There are also provided a number N of XOR gates XOR1 . . . XORn, . . . , XORNxe2x88x921, XORN. A bit stream SI is input serially to the XOR gate XORN. Essentially, depending on the selection of N and an in equation (1a), XOR gates are provided between each two shift registers Cn, Cnxe2x88x921. Depending on the feedbacks from the XOR gate XORN to the individual shift registers (flip-flops) C, a desired CRC code is output from the shift register CNxe2x88x921 of the final stage.
Thus, the designer selects the CRC code to be generated by selecting the feedbacks, i.e. by selecting N and which of the coefficients an are 0 or 1 depending on the desired CRC code. In the circuit in FIG. 1a this selection of coefficients an is reflected by the feedback and the insertion of the particular XOR gates between respective two shift registers.
The operation of the circuit in FIG. 1a is as follows. The input bit stream SI of X bits (is for example 100) is serially input to the XOR gate XORN at sequential clock cycles. Thereafter the CRC code stored in the serial shift registers is serially read out. This means, that after using X clocks cycles to clock the X bits into the CRC circuit, another N clock cycles must be used to serially read out the generated CRC code. The read out CRC code is then serially appended to the user data of X bits to be transmitted together with the user data to the receiver.
Therefore, using the serial CRC generation circuit of FIG. 1a, an additional N clock cylces are always needed to read out the generated CRC code, which increases the processing time for generating and transmitting the CRC code.
FIG. 1b shows an example of the serial CRC circuit for a special CRC 13 code. That is, in FIG. 1b the polynomial is chosen as:
CRC13=X13+X12+X7+X6+X5+X4+X2+1xe2x80x83xe2x80x83(1b)
as shown in FIG. 1b above the serial CRC circuit. Thus, in the circuit of FIG. 1b, N=13 and a13=a12=a7=a6=a5=a4=a2=a0=1. The selection of these coefficients in the CRC polynomial is reflected in the circuit configuration by the feedbacks from the shift register C12 to the other shift registers C0-C11 via the respective XOR gates between the individual shift register C. In FIG. 1b the CRC having length 13 is output serially at the xe2x80x9cCRC 13 serial outxe2x80x9d after the X bits have been serially input.
Since in the circuits in FIG. 1a and FIG. 1b the processing is performed serially, the processing time is increased. Therefore an alternative solution is to perform the generation of the CRC code parallely for a data packet of T bits which is a parallel part of the X serial bits. FIG. 1c shows a general configuration of a parallel CRC generation circuit.
In FIG. 1c an input register means I having T input registers I0, I1, . . . It . . . ITxe2x88x921 for simultaneously storing T input bits is provided. Each input register has an output line I(0), I(1), . . . I(t) . . . I(Txe2x88x921) which leads to a coupling means CM. An output register means C has N output registers C0, C1, . . . Cn . . . , CNxe2x88x921 for parallely storing the generated CRC code. Each of the output registers has an input line C0(T), C1(T), . . . , Cn(T) . . . CNxe2x88x921(T) and an output line C0(0), C1(0) . . . Cn(0) . . . CNxe2x88x921(0). Furthermore, there are provided a number N of parallel XOR gates XOR0, XOR1 . . . XORn . . . XORNxe2x88x921 each having an output connected to a respective input line of the output registers and a number of input lines coupled to the coupling means CM. The output lines of the respective output registers are also input to the coupling means CM.
The operation of the parallel CRC generation circuit in FIG. 1c is as follows. From the data stream of X bits, a number of T bits are input (parallely) to the input register means I. The coupling means CM determines which of the outputs lines from the input register means I and which of the output lines from the output registers C are input to the respective XOR gates. The coupling means does not xe2x80x9ccouplexe2x80x9d the outputs from the input registers and the outputs of the output registers but merely determines which of the input lines of the XOR gates must receive a separate input from the respective input and output registers. In one clock cylce the output registers C contain a parallely generated CRC code. Then, in the next clock cycle the next set of T input bits are input to the input register means I. Then they are input to the XOR gates in combination with the previous CRC code held in the output registers C. Thus, for every T input bits only one clock cycle is needed to parallely generate the CRC code. By contrast to the serial circuits in FIG. 1a and FIG. 1b, where the serial generation of the CRC code takes a large amount of time and is therefore undesirable, the parallel generation circuit of FIG. 1c builds the CRC value for the number T of input bits in one clock cycle.
However, generally the design of the coupling means CM which determines which of the output lines of the input register and output lines of the output registers need to be supplied as inputs to the respective XOR gates is not a trivial task. That is, what has been done with internal state shifting in a serial input register now needs to be performed in one step parallely in FIG. 1c. Conventional design tools performxe2x80x94for a given polynomial and length of the CRCxe2x80x94a simulation of a serial CRC circuit to find out how the individual entries in the serial shift registers change successively with the input of the T bits. On the basis of these simulations the coupling means is determined.
The inventor has performed simulations for designing (i.e. developing and generating) the parallel CRC circuit in such a way and discovered the problem, that the conventional coupling means CM has the disadvantage, that in fact too many feedbacks from the output registers are used. That is, since the conventional simulation tools look at each flip-flop (shift register) of the serial CRC circuit individually, it was discovered that they cannot detect that a possible redundancy exists, i.e. that too many feedbacks from the output registers or too many output lines of the input shift registers I are input to the XOR gates. This redundancy was found to increase the processing time and the hardware amount necessary in the parallel CRC generation circuit. Thus, depending on the used polynomial some of the feedbacks of signals are actually superfluous and the design tools so far have not recognized them as being unnecessary.
The invention is based on the realization of the problem thatxe2x80x94depending on the used polynomialxe2x80x94not all feedbacks and not all outputs from the input registers are necessary as inputs for the XOR gatesxe2x80x94and that it is sufficient for the parallel calculation of the CRC to consider only some of the previous values stored in the output registers.
Thus, the unknown problem perceived by the inventor is
to provide a method and a parallel CRC generation circuit which result in a higher processing speed whilst decreasing the hardware amount necessary for the realization of the parallel CRC generation circuit.
This problem is solved by a method according to claim 1 and a parallel CRC generation circuit according to claim 2.
According to the invention, a two dimensional (time-space) matrix representation of how all entries of a serial shift register for a given CRC polynomial change is stored in a memory. In this matrix representation indications are stored which essentially represent the internal states and the change of internal states indicated by the selected polynomial. This can be seen to be equivalent to the change of internal states (values stored in the shift registers) of a corresponding serial CRC generation circuit.
A special search technique is used to evaluate this matrix representation in order to cancel internal state transitions that occur twice for the same bit. That is, the search method evaluates the matrix represenation in such a way that internal states or input bits which would be input simultaneously to an XOR gate in the parallel circuit are cancelled, since an XOR combination of two identical states (input register output line or output register output line) does not lead to a change of an output signal of the respective XOR gate. Based on this realization, feedbacks from the output registers and/or input bits that do not lead to a change in the output signal are cancelled. Since the number of feedbacks from the output registers and the number of inputs from the input registers is reduced the processing time is decreased and the hardware amount necessary for the parallel CRC circuit is decreased.
Conventional design tools which only evaluate the internal states of each serial shift register in a serial CRC circuit cannot realize this double inputting of values to an XOR gate since they only evaluate individually the states in each serial shift register. Therefore, the invention provides a significant advantage in processing time and hardware amount reduction.
The method for generating a parallel CRC generation circuit automatically provides a parallel CRC circuit for any desired CRC code (predetermined CRC polynomial).
Furthermore, according to a further embodiment of the invention, the method automatically produces a VHDL code needed for manufacturing ASICs or FPGAs. A code output by the method will then be used for loading the respective FPGA. The ASICs and the FPGAs thus obtained have a much increased processing speed and a reduced hardware amount.
The invention can be used in any communication or transmission system where a CRC code is transmitted which must be generated at high speed.